package com.vdimitr.happycube.puzzle;

import java.util.ArrayList;
import java.util.List;

import com.vdimitr.happycube.puzzle.piece.PuzzlePiece;
import com.vdimitr.happycube.puzzle.piece.PuzzlePieceColor;
import com.vdimitr.happycube.puzzle.piece.PuzzlePieceConstants;
import com.vdimitr.happycube.puzzle.piece.construction.PuzzlePieceFactory;
import com.vdimitr.happycube.puzzle.piece.match.PuzzlePieceMatcher;
import com.vdimitr.happycube.puzzle.solution.output.IPuzzlePieceSolutionOutput;

/**
 * This class is responsible for generating the solutions (one or more) of a
 * cube of specific color. It contains the main algorithm for finding solutions
 * and possibly exporting them. </br> N.B. It all starts here!!!
 * 
 * @author vasileios.dimitriadis
 * 
 */
public class CubeSolver {

	/**
	 * Holds the number of total solutions found
	 */
	private int solutionCoutner = 0;

	/**
	 * Holds the number of total attempts to find solutions.
	 */
	private int attemptCounter = 0;

	/**
	 * Flag to indicate if only one solution should be calculated
	 */
	private boolean onlyOneSolution = false;

	/**
	 * Generates the {@link PuzzlePiece}s needed to calculation the solution
	 */
	private PuzzlePieceFactory puzzlePieceFactory = PuzzlePieceFactory
			.getInstance();

	/**
	 * Determines if a {@link PuzzlePiece} is part of the solution
	 */
	private PuzzlePieceMatcher matcher = new PuzzlePieceMatcher();

	/**
	 * If not null, then exports a solution found.
	 */
	private IPuzzlePieceSolutionOutput output;

	/**
	 * Set if only one solution should be calculated
	 * 
	 * @param onlyOneSolution
	 *            true for one solution
	 */
	public void setOnlyOneSolution(boolean onlyOneSolution) {
		this.onlyOneSolution = onlyOneSolution;
	}

	/**
	 * Set the output mechanism to be used for exporting a solution. If null
	 * then no export.
	 * 
	 * @param output
	 *            all solutions found will be passed on to this
	 */
	public void setOutput(IPuzzlePieceSolutionOutput output) {
		this.output = output;
	}

	/**
	 * Get total number of solutions found
	 * 
	 * @return total solutions found
	 */
	public int getSolutionCoutner() {
		return solutionCoutner;
	}

	/**
	 * Get total number of attempts of finding solutions
	 * 
	 * @return total number of attempts
	 */
	public int getAttemptCounter() {
		return attemptCounter;
	}

	/**
	 * Default constructor
	 */
	public CubeSolver() {
	}

	/**
	 * Tries to find all possible solutions for a cube of specified color.
	 * 
	 * @param color
	 *            the color ({@link PuzzlePieceColor}) of the cube to find
	 *            solutions for
	 */
	public void solve(PuzzlePieceColor color) {
		List<PuzzlePiece> puzzlePieces = puzzlePieceFactory
				.createPuzzlePieces(color);
		try {
			int startingPosition = 1;
			searchForSolutionsRecursively(puzzlePieces, startingPosition);
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
	}

	/**
	 * Recursive search of solutions that use the specified puzzle pieces. <br>
	 * Algorithm:
	 * <ul>
	 * <li>For each puzzle piece in the list get all possible variations (flip
	 * and rotation)
	 * <li>Try to see which of those variations fits at the specific position of
	 * the constructed solution.
	 * <li>If a variation fits, then search for the rest of the puzzle pieces at
	 * the next position of the constructed solution.
	 * <li>When terminating condition reached, check that solution found is
	 * valid and if possible export.
	 * </ul>
	 * 
	 * @param puzzlePieces
	 *            A list of puzzle pieces to try to combine together in order to
	 *            produce a solution
	 * @param positionCounter
	 *            Used for determining where each puzzle piece that is part of
	 *            the solution should be placed
	 * @throws Exception
	 *             Should anything goes wrong during export
	 */
	private void searchForSolutionsRecursively(List<PuzzlePiece> puzzlePieces,
			int positionCounter) throws Exception {

		// Short-circuit to stop at first solution found
		if (needToShortCiruit()) {
			return;
		}

		// Terminating condition :
		// either we used all puzzle pieces available or we reach the maximum
		// number of puzzle pieces to use;
		if (needToCheckSolution(puzzlePieces, positionCounter)) {
			// last check to see if cube is concrete (i.e. there are no holes)
			checkSolutionAndPrint();
			return;
		}

		// Next attempt
		attemptCounter++;

		// For each puzzle piece try to fit it in the solution
		for (PuzzlePiece puzzlePiece : puzzlePieces) {
			// Get all puzzle piece variations (flip, rotation)
			List<PuzzlePiece> puzzlePieceVariations = getPuzzlePieceVariations(puzzlePiece);
			// For each of those variations, see which one can be added at the
			// the specific position
			for (PuzzlePiece variation : puzzlePieceVariations) {
				// if puzzle piece fits at the specific position then
				// do a recursive call for the rest of the puzzle pieces
				// at the next position
				if (puzzlePieceFits(variation, positionCounter)) {
					// create a new list of puzzle pieces excluding the one that
					// just fitted
					List<PuzzlePiece> subList = new ArrayList<PuzzlePiece>(
							puzzlePieces);
					subList.remove(puzzlePiece);
					// recursive call with input the rest of the puzzle pieces
					// and the next position
					searchForSolutionsRecursively(subList, positionCounter + 1);
				} else {
					// it fails so skip it
				}
			}
		}
		return;
	}

	/**
	 * Check to see if more than one solutions are required
	 * 
	 * @return true if only one solution is required
	 */
	private boolean needToShortCiruit() {
		return (onlyOneSolution && (solutionCoutner == 1));
	}

	/**
	 * Expresses the terminating condition of the recursive search for
	 * solutions.
	 * 
	 * @param puzzlePieces
	 *            how many puzzle pieces are left
	 * @param positionCounter
	 *            have we reached the maximum position in the solution
	 * @return true if either we have no more puzzle pieces to use or we
	 *         surpassed the maximum position in the solution
	 */
	private boolean needToCheckSolution(List<PuzzlePiece> puzzlePieces,
			int positionCounter) {
		return (puzzlePieces.isEmpty() || positionCounter >= PuzzlePieceConstants.MAXIMUM_NUMBER_OF_PUZZLEPIECES);
	}

	/**
	 * Check if the solution found is valid (an extra check just to make sure)
	 * and export if {@code output} is set
	 * 
	 * @throws Exception
	 *             if something goes wrong during export
	 */
	private void checkSolutionAndPrint() throws Exception {
		if (matcher.isSolutionValid()) {
			// If no output specified then skip and keep on counting
			if (output != null) {
				output.print(matcher.getSolution());
			}
			solutionCoutner++;
		}
	}

	/**
	 * Check if the given puzzle piece can be inserted in the specified position
	 * in the solution. This method helps generate the solution by trying to fit
	 * puzzle pieces to certain positions.
	 * 
	 * @param puzzlePiece
	 *            the puzzle piece to test if it is a possible fit
	 * @param position
	 *            the position in the solution that this puzzle piece could be
	 *            placed if it fits
	 * @return true if the puzzle piece fits in the specified position of the
	 *         solution
	 */
	private boolean puzzlePieceFits(PuzzlePiece puzzlePiece, int position) {
		return matcher.puzzlePieceFits(puzzlePiece, position);
	}

	/**
	 * Generates all the possible variations of a puzzle piece based on rotation
	 * ({@link PuzzlePieceRotation}) and flip ({@link PuzzlePieceFlip})
	 * 
	 * @param puzzlePiece
	 *            the puzzle piece to use for generating all possible variations
	 * @return a list containing puzzle pieces which correspond to the input
	 *         puzzle piece variations
	 */
	private List<PuzzlePiece> getPuzzlePieceVariations(PuzzlePiece puzzlePiece) {
		return puzzlePieceFactory.createPuzzlePieceVariations(puzzlePiece);
	}

}
